package junior.回溯法;

import java.util.Date;

/**
 * 3个元素中，取4个允许重复的组合，组合数：C（4+3-1,4） = 15
 * 3个元素中，取4个允许重复的排列，排列数：81
 * 向量空间：1-2-3，解的长度：n=4，解空间:[ ]
 * 确定解空间：有长度为n的0-1向量组成，包含解空间对改变量的所有可能的 0-1 赋值
 * n=3时，解空间为：（0,0,0）.（0,1,0）...（1,1,0）...（1,1,1）
 *                        根节点
 *                  1               0
 *              1       0       1       0
 *           1   0    1   0   1   0   1   0
 * 解决题型：求子集，0-1背包，多重背包，装载问题
 *
 */
public class 回溯算法框架_允许重复排列_重要 {
    static int[] stack = new int[1000000];
    static int top = 0;
    static int total = 0;
    static int depth = 3;
    public static void main(String[] args) {
        dfs(0);
        System.out.println("total:"+total);
        Date date = new Date();
    }

    /**
     * 2个元素，可重复的取3个，进行全排列（元素，可以重复，且有顺序排列）
     * @param n
     */
    public static void dfs(int n){
        if(n == depth){     // 重复取值的个数
            show();
            total++;
            return;
        }
        for (int i = 0; i <= 4; i++) { // 元素个数
            // 剪枝操作
            stack[top++] = i;
            dfs(n+1);
            top--;
        }
    }
    public static void show(){      // 展示每一次的结果
        for (int i = 0; i < top; i++) {
            System.out.print(stack[i]+"\t");
        }
        System.out.println();
    }
}
